<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>Binary Tree</title>
  <style>
    .root {
      display: flex;
      border: 1px solid #000;
      width: 600px;
      margin: 0 auto;
      height: 150px;
      align-items: center;
      justify-content: center;
    }

    .root div {
      display: flex;
      height: 70%;
      width: 44%;
      margin: 0 3%;
      border: 1px solid #000;
      justify-content: center;
      align-items: center;
      background: #fff;
    }
  </style>
</head>
<body>
<div class="root">
  1

  <div>2
    <div>4</div>
    <div>5</div>
  </div>

  <div>3
    <div>6</div>
    <div>7</div>
  </div>
</div>
</body>

<script>
  /**
   * 深度优先遍历的递归写法
   * 原理：递归的回溯性
   */
  class TravelTree {
    constructor() {
      this.nodeList = [];
    }

    preOrder = node => {
      if (node) {
        this.nodeList.push(node.firstChild.textContent.trim());
        this.preOrder(node.firstElementChild);
        this.preOrder(node.lastElementChild);
      }
    };

    inOrder = node => {
      if (node) {
        this.inOrder(node.firstElementChild);
        this.nodeList.push(node.firstChild.textContent.trim());
        this.inOrder(node.lastElementChild);
      }
    };

    postOrder = node => {
      if (node) {
        this.postOrder(node.firstElementChild);
        this.postOrder(node.lastElementChild);
        this.nodeList.push(node.firstChild.textContent.trim());
      }
    };

    reset() {
      this.nodeList = [];
    }

  }

  let node = document.querySelector('.root');
  let tree = new TravelTree();

  console.log('TravelTree');
  tree.reset();
  tree.preOrder(node);
  console.log(tree.nodeList);

  tree.reset();
  tree.inOrder(node);
  console.log(tree.nodeList);

  tree.reset();
  tree.postOrder(node);
  console.log(tree.nodeList);

  // 深度优先遍历的非递归写法
  class StackTree {
    constructor() {
      this.nodeList = [];
      this.stack = []
    }


    preOrder(node) {
      let treeNode = node;
      while (treeNode || this.stack.length) {
        // 进栈 将所有左节点压栈
        while (treeNode) {
          this.stack.push(treeNode);
          this.nodeList.push(treeNode.firstChild.textContent.trim());
          treeNode = treeNode.firstElementChild;
        }
        // 出栈
        if (this.stack.length) {
          treeNode = this.stack.pop();
          treeNode = treeNode.lastElementChild;
        }
      }
    }

    inOrder(node) {
      let treeNode = node;
      while (treeNode || this.stack.length) {
        while (treeNode) {
          this.stack.push(treeNode);
          treeNode = treeNode.firstElementChild;
        }
        if (this.stack.length) {
          treeNode = this.stack.pop();
          this.nodeList.push(treeNode.firstChild.textContent.trim());
          treeNode = treeNode.lastElementChild;
        }
      }
    }

    /*
    *  将根节点压入第一个栈
    *  从第一个栈中弹出一个元素，压入第二个栈
    *  然后分别将该节点的左右孩子压入第一个栈
    *  重复步骤2和步骤3直到第一个栈为空
    *  执行结束，第二个栈中就保存了所有节点的后序遍历输出结果。依次将元素从第二个栈中弹出即可。
    */

    postOrder(node) {
      let treeNode = node;
      this.stack.push(treeNode);
      while (this.stack.length) {
        treeNode = this.stack.pop();
        this.nodeList.unshift(treeNode.firstChild.textContent.trim());

        if (treeNode.firstElementChild) {
          this.stack.push(treeNode.firstElementChild)
        }
        if (treeNode.lastElementChild) {
          this.stack.push(treeNode.lastElementChild)
        }
      }
    }

    reset() {
      this.stack = [];
      this.nodeList = [];
    }

  }

  let stackTree = new StackTree();
  console.log('stackTree');

  stackTree.preOrder(node);
  console.log(stackTree.nodeList);

  stackTree.reset();
  stackTree.inOrder(node);
  console.log(stackTree.nodeList);

  stackTree.reset();
  stackTree.postOrder(node);
  console.log(stackTree.nodeList);

  // 广度度优先遍历非递归
  class WidthTravelTree {
    constructor() {
      this.nodeList = [];
      this.stack = []
    }

    // 队列
    widthTravel(node) {
      if (node) {
        this.stack.push(node);
        this.nodeList.push(node.firstChild.textContent.trim());
        while (this.stack.length) {
          let item = this.stack.shift();
          if (item.firstElementChild) {
            this.nodeList.push(item.firstElementChild.firstChild.textContent.trim());
            this.stack.push(item.firstElementChild);
          }
          if (item.lastElementChild) {
            this.nodeList.push(item.lastElementChild.firstChild.textContent.trim());
            this.stack.push(item.lastElementChild)
          }
        }
      }
    }
  }


  console.log('WidthTravelTree');
  let widthTravelTree = new WidthTravelTree();
  widthTravelTree.widthTravel(node);
  console.log(widthTravelTree.nodeList);

</script>
</html>
